import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        String[] arr = new String[]{"i","love","leetcode","i","love","coding"};
        for(String e: s.topKFrequent(arr, 3)) {
            System.out.print(e + " ");
        }
    }

    public List<String> topKFrequent1(String[] words, int k) {
        /**
         * 前k个高频单词
         *  解法一：使用比较器求得前k个符合要求的元素
         *  使用map计数，后使用entreSet进行排序*/
        // 1 预处理
        HashMap<String, Integer> map = new HashMap<>();
        for(String e: words) {
            map.put(e, map.getOrDefault(e, 0) + 1);
        }

        // 2 比较
        Set<Map.Entry<String, Integer>> entreSet = map.entrySet();
        List<Map.Entry<String, Integer>> entryList = new ArrayList<>(entreSet);
        // -排序
        /**
         * 按照出现频率排降序，若是频率相同，则按照单词排字典序
         * e1 - e2 默认为升序，e2 - e1为降序
         * */
        entryList.sort((e1, e2) -> {
            int valueCompare = e2.getValue() - e1.getValue();
            return valueCompare != 0 ? valueCompare : e1.getKey().compareTo(e2.getKey());
        });

        // 3 返回值
        List<String> retList = new ArrayList<>();
        int i = 0;
        for(Map.Entry<String, Integer> e: entryList) {
            if(i == k) {
                break;
            }
            retList.add(e.getKey());
            i++;
        }
        return retList;
    }

    public List<String> topKFrequent(String[] words, int k) {
        /**
         * 前k个高频单词
         *  解法二：使用堆处理，在入堆时进行比较*/
        // 1 预处理
        HashMap<String, Integer> map = new HashMap<>();
        for(String e: words) {
            map.put(e, map.getOrDefault(e, 0) + 1);
        }

        // 2 使用堆处理Top k问题
        // -需要给优先级队列传递比较器（由于要反转，因此比较器都需要传递反向的）
        // -我们真实比较需求为：按照出现频率排降序，若是频率相同，则按照单词排字典序
        // -而由于每次都是从小根堆堆顶拿元素尾插，后续要反转数组，故比较器传递反向比较，即：按照出现频率排升序，若是频率相同，则按照单词字典序排倒序
        PriorityQueue<Map.Entry<String, Integer>> heap = new PriorityQueue<>((e1, e2) -> {
            int compareValue = e1.getValue() - e2.getValue();
            return compareValue == 0 ? e2.getKey().compareTo(e1.getKey()) : compareValue;
        });
        for(Map.Entry<String, Integer> e: map.entrySet()) {
            heap.offer(e);
            if(heap.size() > k) {
                heap.poll();
            }
        }

        // 3 返回值
        List<String> retList = new ArrayList<>();
        while(!heap.isEmpty()) {
            retList.add(heap.poll().getKey());
        }
        // -由于从堆顶尾插，故此时为升序，我们处理成降序即可
        Collections.reverse(retList);
        return retList;
    }
}
